#!/usr/bin python3
# -*- coding: utf-8 -*-

from typing import List
from enum import Enum


class Algrithom(Enum):
    RECURSION = 0
    LOOP = 1


def chop(data: int, dataset: List[int], lo=0, hi=None, alg=Algrithom.LOOP) -> int:
    if len(dataset) == 0:
        return -1
    if hi is None:
        hi = len(dataset) - 1
    
    if alg == Algrithom.RECURSION:
        return _binary_search_recursion(data, dataset, lo, hi)
    elif alg == Algrithom.LOOP:
        return _binary_search_loop(data, dataset, lo, hi)


def _binary_search_recursion(k: int, dataset: List[int], lo: int, hi: int) \
        -> int:
    if lo > hi:
        return -1

    mid = (lo + hi) // 2
    if k == dataset[mid]:
        return mid
    elif k > dataset[mid]:
        return _binary_search_recursion(k, dataset, mid+1, hi)
    elif k < dataset[mid]:
        return _binary_search_recursion(k, dataset, lo, mid-1)


def _binary_search_loop(k: int, dataset: List[int], lo: int, hi: int) \
        -> int:
    for _ in range(lo, hi + 2):  # 保证至少循环两次, 处理dataset长度等于0和1的边界条件
        if lo > hi:
            return -1

        mid = (lo + hi) // 2

        if k == dataset[mid]:
            return mid
        elif k > dataset[mid]:
            lo = mid + 1
        elif k < dataset[mid]:
            hi = mid - 1
